import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 死锁检测器 类
 */
public class DeadlockDetector {

    private List<ResourceType> resourceTypeList;
    private List<ResourceAllocation> resourceAllocationList;
    private List<ProcessWait> processWaitList;

    public DeadlockDetector() {
        resourceTypeList = new ArrayList<>();
        resourceAllocationList = new ArrayList<>();
        processWaitList = new ArrayList<>();
    }

    // 注册资源类
    public void registerResource(int resourceId, int totalInstances) {
        resourceTypeList.add(new ResourceType(resourceId, totalInstances));
        System.out.println(resourceTypeList.get(resourceTypeList.size() - 1));
    }

    // 分实例给进程
    public boolean allocateResource(int processId, int resourceId, int allocatedInstances) {

        ResourceType resourceType = findResourceType(resourceId);

        if (resourceType == null) {
            System.out.println("R" + resourceId + " 资源不存在~");
            return false;
        }

        System.out.print("P" + processId + " 正在向 R" + resourceId + " 请求实例, ");

        if (resourceType.getAvailableInstances() >= allocatedInstances) {

            // 成功分配
            resourceType.setAvailableInstances(resourceType.getAvailableInstances() - allocatedInstances);
            resourceAllocationList.add(new ResourceAllocation(resourceId, processId, allocatedInstances));
            System.out.printf("请求成功: R%d×%d -> P%d\n",
                    resourceId, allocatedInstances, processId);
            return true;
        } else {

            // 实例数量太少, 分配不成功
            System.out.printf("请求失败: R%d 可用%d个, 但 P%d 需要%d个\n",
                    resourceId, resourceType.getAvailableInstances(),
                    processId, allocatedInstances);
            return false;
        }

    }

    // 进程向资源请求实例
    public void requestResource(int processId, int resourceId, int allocatedInstances) {
        if (allocateResource(processId, resourceId, allocatedInstances)) {
            // 分配成功
            return;
        }

        // 分配失败, 加入进程等待记录
        processWaitList.add(new ProcessWait(processId, resourceId, allocatedInstances));
        System.out.printf("P%d 加入等待队列: %s\n",
                processId, processWaitList.get(processWaitList.size() - 1));

        // 进行死锁检测
        if (!detectDeadlock(processId)) {
            System.out.println("无死锁, 进程正常等待~");
            return;
        }
        // 发现死锁, 进行死锁解除
        resolveDeadlock();
    }

    /**
     * 死锁检测方法
     * @param processId 开始检测的进程 id
     * @return false : 无死锁, true : 存在死锁
     *
     * 要是将每一个进程和资源点看成是顶点, 进程和资源的分配关系看成是边
     * 那么这就是一个图了
     * 那么这里检测时候有死锁的算法思路就是检查图是否成环, 要是成环说明进程
     * 获取资源就是相互等待的, 那么形成了死锁
     * 这里用 dfs 来遍历第一个顶点相关联的每一个顶点, 用 visited 来记录走
     * 过的顶点, 要是在下面的 dfs 中遍历到了, 就说明是成环了的, 再用 path
     * 记录走过的路, 打印环的基本信息, 为下面死锁的解除记录信息
     */
    private boolean detectDeadlock(int processId) {
        Set<Integer> visited = new HashSet<>();
        List<Integer> path = new ArrayList<>();
        System.out.println("开始死锁检测~, 从进程 P" + processId + " 开始...");
        return dfsDetect(processId, visited, path);
    }

    // 死锁解除策略
    private void resolveDeadlock() {
        System.out.println("进行死锁解除:");

        if (!processWaitList.isEmpty()) {
            ProcessWait wait = processWaitList.get(processWaitList.size() - 1);
            System.out.println("终止进程 P" + wait.getProcessId() + " 来解除死锁");

            // 释放该进程占用的所有资源
            releaseProcessResources(wait.getProcessId());
            // 从等待表中移除
            processWaitList.remove(wait);
        }
    }

    // 释放进程占用的所有资源
    private void releaseProcessResources(int processId) {

        // 在 resourceAllocationList 查找进程 id 相同的记录
        for (ResourceAllocation resourceAllocation : resourceAllocationList) {

            if (resourceAllocation.getProcessId() == processId) {

                // 找到了释放这个记录所占用的资源
                ResourceType resourceType = findResourceType(resourceAllocation.getProcessId());

                // 资源不为 null, 就释放
                if (resourceType != null) {

                    resourceType.setAvailableInstances(resourceType.getAvailableInstances()
                            + resourceAllocation.getAllocationInstances());

                    System.out.printf("释放: P%d 的 R%d×%d\n",
                            processId, resourceAllocation.getResourceId(),
                            resourceAllocation.getAllocationInstances());
                }
            }
        }
    }

    private boolean dfsDetect(int processId, Set<Integer> visited, List<Integer> path) {

        // 深搜出口
        if (visited.contains(processId)) {

            // 环的起点
            int cycleStart = path.indexOf(processId);

            // 环 list
            List<Integer> cycle = path.subList(cycleStart, path.size());

            // 这里在末尾添加一个起点
            cycle.add(processId);

            System.out.println("检测到死锁!");
            System.out.print("发现死锁环路: ");

            for (int i = 0; i < cycle.size(); i++) {
                System.out.print("P" + cycle.get(i));
                if (i < cycle.size() - 1) System.out.print(" → ");
            }
            System.out.println();
            return true;
        }

        visited.add(processId);
        path.add(processId);

        // 既然这个进程是要加入等待队列的, 那我们就需要检测它加入等待队列之后
        // 是否会和别的进程形成等待环, 那么我们就需要找出和它使用同一个资源的
        // 的进程, 那么先查找有关这个进程的等待记录
        List<ProcessWait> waitList = getWaitList(processId);

        for (ProcessWait wait : waitList) {
            // 通过资源在资源分配类中找出和它有相同资源的进程
            List<Integer> processList = getProcess(wait.getResourceId());
            for (int curProcessId : processList) {
                if (curProcessId != processId) { // 避免自循环

                    // 存在就深搜
                    if (dfsDetect(curProcessId, visited, path)) {

                        // 存在死锁就返回 true
                        return true;
                    }
                }
            }
        }

        // 恢复现场
        visited.remove(processId);
        path.remove(path.size() - 1);

        // 没有死锁
        return false;
    }

    // 获取有相同资源的进程 id
    private List<Integer> getProcess(int resourceId) {
        List<Integer> result = new ArrayList<>();
        for (ResourceAllocation alloc : resourceAllocationList) {
            if (alloc.getResourceId() == resourceId) {
                result.add(alloc.getProcessId());
            }
        }
        return result;
    }

    // 获取进程等待的所有资源
    private List<ProcessWait> getWaitList(int processId) {
        List<ProcessWait> result = new ArrayList<>();
        for (ProcessWait wait : processWaitList) {
            if (wait.getProcessId() == processId) {
                result.add(wait);
            }
        }
        return result;
    }

    // 查找资源
    private ResourceType findResourceType(int resourceId) {
        for (ResourceType resourceType : resourceTypeList) {
            if (resourceType.getResourceId() == resourceId) {
                return resourceType;
            }
        }
        return null;
    }

    // 打印系统状态
    public void printSystemStatus() {
        System.out.println("=== 系统当前状态 ===");

        System.out.println("资源类型:");
        if (resourceTypeList.isEmpty()) {
            System.out.println("  no data");
        }
        for (ResourceType resource : resourceTypeList) {
            System.out.println("  " + resource);
        }

        System.out.println("资源分配:");
        if (resourceAllocationList.isEmpty()) {
            System.out.println("  no data");
        }
        for (ResourceAllocation alloc : resourceAllocationList) {
            System.out.println("  " + alloc);
        }

        System.out.println("进程等待:");
        if (processWaitList.isEmpty()) {
            System.out.println("  no data");
        }
        for (ProcessWait wait : processWaitList) {
            System.out.println("  " + wait);
        }
        System.out.println("==================");
    }
}
